What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization

摘要

Using different methods for laying out a graph can lead to very differentvisual appearances, with which the viewer perceives different information.Selecting a "good" layout method is thus important for visualizing a graph. Theselection can be highly subjective and dependent on the given task. A commonapproach to selecting a good layout is to use aesthetic criteria and visualinspection. However, fully calculating various layouts and their associatedaesthetic metrics is computationally expensive. In this paper, we present amachine learning approach to large graph visualization based on computing thetopological similarity of graphs using graph kernels. For a given graph, ourapproach can show what the graph would look like in different layouts andestimate their corresponding aesthetic metrics. An important contribution ofour work is the development of a new framework to design graph kernels. Ourexperimental study shows that our estimation calculation is considerably fasterthan computing the actual layouts and their aesthetic metrics. Also, our graphkernels outperform the state-of-the-art ones in both time and accuracy. Inaddition, we conducted a user study to demonstrate that the topologicalsimilarity computed with our graph kernel matches perceptual similarityassessed by human users.